﻿/******************************************************************************
 * 
 * Announce: CSharpKit, Basic algorithms, components and definitions.
 *           Copyright (C) ShenYongchen.
 *           All rights reserved.
 *   Author: 申永辰.郑州 (shenyczz@163.com)
 *  WebSite: http://github.com/shenyczz/CSharpKit
 *
 * THIS CODE IS LICENSED UNDER THE MIT LICENSE (MIT).
 * THIS CODE IS PROVIDED *AS IS* WITHOUT WARRANTY OF 
 * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING ANY
 * IMPLIED WARRANTIES OF FITNESS FOR A PARTICULAR
 * PURPOSE, MERCHANTABILITY, OR NON-INFRINGEMENT.
 * 
******************************************************************************/

using System;
using System.Collections.Generic;
using System.Runtime.Serialization;

namespace CSharpKit.Numerics.LinearAlgebra
{
    /// <summary>
    /// 稀疏矢量存储器
    /// </summary>
    /// <typeparam name="T"></typeparam>
    [Serializable]
    public class VectorStorageSparse<T> : VectorStorage<T>
        where T : struct, IFormattable, IEquatable<T>
    {
        #region Constructors

        public VectorStorageSparse(int length)
            : base(length)
        {
            Indices = new int[0];
            Values = new T[0];
            ValueCount = 0;

            _IsDense = false;
        }

        #endregion

        /// <summary>
        /// 非零值索引
        /// </summary>
        [DataMember(Order = 1)]
        public int[] Indices;

        /// <summary>
        /// 非零值元素(element)
        /// </summary>
        [DataMember(Order = 2)]
        public T[] Values;

        /// <summary>
        /// 非零值元素数量
        /// </summary>
        [DataMember(Order = 3)]
        public int ValueCount;

        internal override T At(int index)
        {
            // Search if item index exists in NonZeroIndices array in range "0 - nonzero values count"
            var itemIndex = Array.BinarySearch(Indices, 0, ValueCount, index);
            return itemIndex < 0 ? Zero : Values[itemIndex];
        }

        internal override void At(int index, T tvalue)
        {
            // Search if "index" already exists in range "0 - nonzero values count"
            var itemIndex = Array.BinarySearch(Indices, 0, ValueCount, index);
            if (itemIndex < 0)
            {
                // Item not found and !=0, then Add new value
                if (!Zero.Equals(tvalue))
                {
                    InsertAtIndexUnchecked(~itemIndex, index, tvalue);
                }
            }
            else
            {
                if (Zero.Equals(tvalue))
                {
                    // Delete existing item
                    RemoveAtIndexUnchecked(itemIndex);
                }
                else
                {
                    // Update item
                    Values[itemIndex] = tvalue;
                }
            }
        }

        internal void InsertAtIndexUnchecked(int itemIndex, int index, T value)
        {
            // Check if the storage needs to be increased
            if ((ValueCount == Values.Length) && (ValueCount < Length))
            {
                // Value and Indices arrays are completely full so we increase the size
                var size = System.Math.Min(Values.Length + GrowthSize(), Length);
                Array.Resize(ref Values, size);
                Array.Resize(ref Indices, size);
            }

            // Move all values (with a position larger than index) in the value array to the next position
            // Move all values (with a position larger than index) in the columIndices array to the next position
            Array.Copy(Values, itemIndex, Values, itemIndex + 1, ValueCount - itemIndex);
            Array.Copy(Indices, itemIndex, Indices, itemIndex + 1, ValueCount - itemIndex);

            // Add the value and the column index
            Values[itemIndex] = value;
            Indices[itemIndex] = index;

            // increase the number of non-zero numbers by one
            ValueCount += 1;
        }

        internal void RemoveAtIndexUnchecked(int itemIndex)
        {
            // Value is zero. Let's delete it from Values and Indices array
            Array.Copy(Values, itemIndex + 1, Values, itemIndex, ValueCount - itemIndex - 1);
            Array.Copy(Indices, itemIndex + 1, Indices, itemIndex, ValueCount - itemIndex - 1);

            ValueCount -= 1;

            // Check whether we need to shrink the arrays. This is reasonable to do if
            // there are a lot of non-zero elements and storage is two times bigger
            if ((ValueCount > 1024) && (ValueCount < Indices.Length / 2))
            {
                Array.Resize(ref Values, ValueCount);
                Array.Resize(ref Indices, ValueCount);
            }
        }






        /// <summary>
        /// 生长大小 ?
        /// </summary>
        /// <returns></returns>
        private int GrowthSize()
        {
            int delta;
            if (Values.Length > 1024)
            {
                delta = Values.Length / 4;
            }
            else
            {
                if (Values.Length > 256)
                {
                    delta = 512;
                }
                else
                {
                    delta = Values.Length > 64 ? 128 : 32;
                }
            }

            return delta;
        }








        // STATIC FUNCTIONS

        public static VectorStorageSparse<T> OfValue(int length, T value)
        {
            if (Zero.Equals(value))
            {
                return new VectorStorageSparse<T>(length);
            }

            if (length < 1)
            {
                throw new ArgumentOutOfRangeException(nameof(length), string.Format(Resources.Numerics.ArgumentLessThanOne, length));
            }

            var indices = new int[length];
            var values = new T[length];
            for (int i = 0; i < indices.Length; i++)
            {
                indices[i] = i;
                values[i] = value;
            }

            return new VectorStorageSparse<T>(length)
            {
                Indices = indices,
                Values = values,
                ValueCount = length
            };
        }
        public static VectorStorageSparse<T> OfInit(int length, Func<int, T> init)
        {
            if (length < 1)
            {
                throw new ArgumentOutOfRangeException(nameof(length), string.Format(Resources.Numerics.ArgumentLessThanOne, length));
            }

            var indices = new List<int>();
            var values = new List<T>();
            for (int i = 0; i < length; i++)
            {
                var item = init(i);
                if (!Zero.Equals(item))
                {
                    values.Add(item);
                    indices.Add(i);
                }
            }
            return new VectorStorageSparse<T>(length)
            {
                Indices = indices.ToArray(),
                Values = values.ToArray(),
                ValueCount = values.Count
            };
        }

        public static VectorStorageSparse<T> OfEnumerable(IEnumerable<T> data)
        {
            if (data == null)
            {
                throw new ArgumentNullException(nameof(data));
            }

            var indices = new List<int>();
            var values = new List<T>();
            int index = 0;

            foreach (T item in data)
            {
                if (!Zero.Equals(item))
                {
                    values.Add(item);
                    indices.Add(index);
                }
                index++;
            }

            return new VectorStorageSparse<T>(index)
            {
                Indices = indices.ToArray(),
                Values = values.ToArray(),
                ValueCount = values.Count
            };
        }






        //}}@@@
    }


}
